import edu.princeton.cs.algs4.BinaryStdOut;

import java.util.Arrays;

public class CircularSuffixArray {
    private final int[] suffix;
    private final String originString;

    // circular suffix array of s
    public CircularSuffixArray(String s) {
        if (s == null || s.length() == 0) {
            throw new IllegalArgumentException("s is not null");
        }
        originString = s;
        suffix = new int[s.length()];
        sortSuffix();
    }

    private void sortSuffix() {
        CircularSuffix[] suffixes = new CircularSuffix[suffix.length];
        for (int i = 0; i < suffixes.length; i++) {
            suffixes[i] = new CircularSuffix(originString, i);
        }
        Arrays.sort(suffixes);
        for (int i = 0; i < suffixes.length; i++) {
            suffix[i] = suffixes[i].offset;
        }
    }

    // length of s
    public int length() {
        return suffix.length;
    }

    // returns index of ith sorted suffix
    public int index(int i) {
        if (i < 0 || i >= suffix.length) {
            throw new IllegalArgumentException("i is illegal");
        }
        return suffix[i];
    }

    private static class CircularSuffix implements Comparable<CircularSuffix> {
        int offset;
        String str;

        CircularSuffix(String str, int offset) {
            this.offset = offset;
            this.str = str;
        }

        @Override
        public int compareTo(CircularSuffix o) {
            int offset1 = this.offset;
            int offset2 = o.offset;

            int k = 0;
            int lim = str.length();
            while (k < lim) {
                char c1 = str.charAt((k + offset1) % lim);
                char c2 = str.charAt((k + offset2) % lim);
                if (c1 != c2) {
                    return c1 - c2;
                }
                k++;
            }
            return 0;
        }
    }

    // unit testing (required)
    public static void main(String[] args) {
        CircularSuffixArray array = new CircularSuffixArray("ABRACADABRA!");
        for (int i = 0; i < array.length(); i++) {
            BinaryStdOut.write(array.index(i) + ",");
        }
    }
}
